﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace eu.h8me.Parsing.LexerLib {

    // Regular expression tree.
    internal class Tree {

        // Delegate helper type.
        public delegate Tree Process(Tree tree);

        // Data.
        private Node _StartNode;
        private Node _EndNode;
        private bool _AtNewLine;
        private Tree _Trailing;
        private bool _Finished;

        // Create a new, empty RETree.
        public Tree() {
            // Empty tree has equivalent start/end nodes (and no transitions on them).
            _StartNode = _EndNode = new Node();
        }

        // Create a new RETree from a character range.
        public Tree(CharRange range) {
            // Attach transition on character range between two nodes.
            _EndNode = new Node();
            _StartNode = new Node(new Transition(range, _EndNode));
        }

        // Create a new tree with the specified nodes.
        private Tree(Node start, Node end) {
            // Apply new tree node.
            _EndNode = end;
            _StartNode = start;
        }

        // Start node accessor.
        public Node StartNode {
            get {
                // Fetch start node.
                Debug.Assert(_Finished, "Trying to access StartNode before finish");
                return _StartNode;
            }
        }

        // End node accessor.
        public Node EndNode {
            get {
                // Fetch end node.
                Debug.Assert(_Finished, "Trying to access EndNode before finish");
                return _EndNode;
            }
        }

        // At new line accessor.
        public bool MatchAtNewLine {
            get {
                // Return newline state.
                Debug.Assert(_Finished, "Trying to access MatchAtNewLine before finish");
                return _AtNewLine;
            }
        }

        // Finish a tree.
        public void Finish() {
            // Check whether we have trailing context.
            Debug.Assert(!_Finished, "Trying to access after finish");
            if( _Trailing != null ) {
                // Attach trailing for now.
                _EndNode.AddEpsilonTransition(_Trailing._StartNode);
                _EndNode = _Trailing._EndNode;
            }

            // Set finished flag.
            _Finished = true;
        }

        // Merge two trees.
        public static Tree operator |(Tree t1, Tree t2) {
            // Check whether one of the trees is empty.
            Debug.Assert(!t1._Finished && !t2._Finished, "Trying to access after finish");
            Tree clone;
            if( t1._StartNode == t1._EndNode ) {
                // Clone second tree.
                clone = t2.Clone(null, null);
                if( t2._StartNode != t2._EndNode )
                    // Second tree isn't empty, make it skippable (ensuring start doesn't have incoming and end doesn't have
                    // outgoing transitions).
                    clone._StartNode.AddEpsilonTransition(clone._EndNode);
            } else if( t2._StartNode == t2._EndNode ) {
                // Clone first tree and make it skippable (it's not empty).
                clone = t1.Clone(null, null);
                clone._StartNode.AddEpsilonTransition(clone._EndNode);
            } else {
                // Copy both trees.
                clone = t1.Clone(null, null);
                Tree clone2 = t2.Clone(null, null);

                // Add dispatch from first clone to second and return copy. The code below keeps the property that start doesn't
                // have incoming and end doesn't have outgoing transitions.
                clone._StartNode.AddEpsilonTransition(clone2._StartNode);
                clone._EndNode.AddEpsilonTransition(clone2._EndNode);
                clone._EndNode = clone2._EndNode;
            }

            // Return clone.
            return clone;
        }

        // Attach one tree to another.
        public static Tree operator +(Tree t1, Tree t2) {
            // Check whether one of the trees is empty.
            Debug.Assert(!t1._Finished && !t2._Finished, "Trying to access after finish");
            Tree clone;
            if( t1._StartNode == t1._EndNode )
                // Clone t2.
                clone = t2.Clone(null, null);
            else {
                // Clone t1 and check whether t2 is non-empty.
                clone = t1.Clone(null, null);
                if( t2._StartNode != t2._EndNode ) {
                    // Need to clone t2 and attach it.
                    Tree clone2 = t2.Clone(null, null);
                    clone._EndNode.AddEpsilonTransition(clone2._StartNode);
                    clone._EndNode = clone2._EndNode;
                }
            }

            // Return clone.
            return clone;
        }

        // Add repetition (*).
        public Tree ZeroOrMore() {
            // Create clone.
            Debug.Assert(!_Finished, "Trying to access after finish");
            Tree clone = Clone(null, null);
            if( _StartNode != _EndNode ) {
                // Create new start and end node.
                Node newstart = new Node();
                Node newend = new Node();

                // Attach transitions (keeping the property that final start doesn't have incoming and final end doesn't have
                // outgoing transitions).
                newstart.AddEpsilonTransition(newend);
                newstart.AddEpsilonTransition(clone._StartNode);
                clone._EndNode.AddEpsilonTransition(clone._StartNode);
                clone._EndNode.AddEpsilonTransition(newend);

                // Finalize start/end nodes.
                clone._StartNode = newstart;
                clone._EndNode = newend;
            }

            // Return the clone.
            return clone;
        }

        // Add repetition (+).
        public Tree OneOrMore() {
            // Create clone.
            Debug.Assert(!_Finished, "Trying to access after finish");
            Tree clone = Clone(null, null);
            if( _StartNode != _EndNode ) {
                // Create new start and end node.
                Node newstart = new Node();
                Node newend = new Node();

                // Attach transition for loop (keeping the property that the final start doesn't have incoming and final end
                // doesn't have outgoing transitions).
                newstart.AddEpsilonTransition(clone._StartNode);
                clone._EndNode.AddEpsilonTransition(clone._StartNode);
                clone._EndNode.AddEpsilonTransition(newend);

                // Finalize start/end nodes.
                clone._StartNode = newstart;
                clone._EndNode = newend;
            }

            // Return the clone.
            return clone;
        }

        // Add repetition (?).
        public Tree ZeroOrOne() {
            // Create clone.
            Debug.Assert(!_Finished, "Trying to access after finish");
            Tree clone = Clone(null, null);
            if( _StartNode != _EndNode )
                // Attach transition for loop.
                clone._StartNode.AddEpsilonTransition(clone._EndNode);

            // Return clone.
            return clone;
        }

        // Add counted repetition.
        public Tree Repeat(RepeatCount cnt) {
            // Check whether tree is empty. If so, no need to add any repetitions.
            Debug.Assert(!_Finished, "Trying to access after finish");
            if( _StartNode == _EndNode )
                return Clone(null, null);

            // Create initial clones (for leading fixed count).
            Tree rv = null;
            Tree laststart = null;
            for( int i = 0; i < cnt.From; ++i ) {
                // Create clone.
                laststart = Clone(null, null);
                if( rv != null ) {
                    // Queue at end.
                    rv._EndNode.AddEpsilonTransition(laststart._StartNode);
                    rv._EndNode = laststart._EndNode;
                } else
                    // Initialize chain.
                    rv = laststart;
            }

            // Check for max.
            if( cnt.HasTo ) {
                // Build tail from end.
                Tree stopchain = null;
                for( int i = cnt.From; i < cnt.To; ++i ) {
                    // Create clone.
                    Tree clone = Clone(null, null);
                    if( stopchain != null ) {
                        // Queue at start and add jumps over stopchain.
                        clone._EndNode.AddEpsilonTransition(stopchain._StartNode);
                        clone._StartNode.AddEpsilonTransition(stopchain._EndNode);
                        clone._EndNode = stopchain._EndNode;
                    } else
                        // Initialize chain.
                        clone._StartNode.AddEpsilonTransition(clone._EndNode);

                    // Copy new node to stop chain.
                    stopchain = clone;
                }

                // Attach stop/start chain if present (at least one is).
                if( rv != null && stopchain != null ) {
                    // Attach them.
                    rv._EndNode.AddEpsilonTransition(stopchain._StartNode);
                    rv._EndNode = stopchain._EndNode;
                } else if( rv == null )
                    // No start-chain, just use stop-chain (which must be present, 0-0 isn't allowed).
                    rv = stopchain;
            } else if( rv != null ) {
                // Create loop on last item, patching in new end (and possibly start) node.
                Node newstart;
                Node newend = new Node();
                if( rv._StartNode == laststart._StartNode ) {
                    // Need to create new start node; front only contains the final leading one.
                    newstart = new Node();
                    newstart.AddEpsilonTransition(rv._StartNode);
                } else
                    // Can use cloned start node already present (won't get incoming nodes).
                    newstart = rv._StartNode;

                // Attach transition to final end node and update start/end.
                rv._EndNode.AddEpsilonTransition(laststart._StartNode);
                rv._EndNode.AddEpsilonTransition(newend);
                rv._StartNode = newstart;
                rv._EndNode = newend;
            } else {
                // Create new start and end node (and tree clone)
                rv = Clone(null, null);
                Node newstart = new Node();
                Node newend = new Node();

                // Attach transitions (keeping the property that final start doesn't have incoming and final end doesn't have
                // outgoing transitions).
                newstart.AddEpsilonTransition(newend);
                newstart.AddEpsilonTransition(rv._StartNode);
                rv._EndNode.AddEpsilonTransition(rv._StartNode);
                rv._EndNode.AddEpsilonTransition(newend);

                // Finalize start/end nodes.
                rv._StartNode = newstart;
                rv._EndNode = newend;
            }

            // Return value.
            return rv;
        }

        // Clone a tree.
        public Tree Clone(CharRange.Process proc, Node.Process nproc) {
            // Create stack for processing.
            Dictionary<Node, Node> clones = new Dictionary<Node, Node>();
            Stack<Node> toprocess = new Stack<Node>();

            // Initialize new start node.
            Node start;
            clones[_StartNode] = start = new Node();
            toprocess.Push(_StartNode);

            // Loop while nodes remain to be processed.
            while( toprocess.Count > 0 )
                toprocess.Pop().Clone(clones, toprocess, proc, nproc);

            // Return new tree with cloned start/end node.
            return new Tree(start, clones[_EndNode]);
        }

        // Print the tree.
        public void Print() {
            // Keep list of nodes, enumerating them and printing them.
            Dictionary<Node, int> numbered = new Dictionary<Node, int>();
            Stack<Node> toprocess = new Stack<Node>();
            int nextidx = 0;

            // Initialize start node.
            int startidx = numbered[_StartNode] = nextidx++;
            toprocess.Push(_StartNode);

            // Loop while nodes remain to be processed.
            while( toprocess.Count > 0 )
                toprocess.Pop().Print(numbered, toprocess, ref nextidx);

            // Print start and end node.
            Console.WriteLine("Start at {0}, end at {1}", startidx, numbered[_EndNode]);
        }

        // Helper for ignorecase.
        public static Tree IgnoreCase(Tree tree) {
            // Return a cloned tree where all dispatches have been made case-insensitive.
            return tree.Clone(CharRange.IgnoreCase, null);
        }

        // Helper for newline matching.
        public static Tree AtNewLine(Tree tree) {
            // Clone tree and set flag to match at newline on clone.
            Tree clone = tree.Clone(null, null);
            clone._AtNewLine = true;
            return clone;
        }

        // Helper method to create a match extension which clones tree and adds trailing context.
        public static Process Trailing(Tree trail) {
            // Return helper delegate.
            return delegate(Tree tree) {
                // Create clone and attach trailing tree, return clone.
                Tree clone = tree.Clone(null, null);
                clone._Trailing = tree._Trailing != null ? tree._Trailing + trail : trail;
                return clone;
            };
        }

    }

    // Tree node.
    internal class Node : IComparable<Node> {

        // Delegate helper type.
        public delegate void Process(Node nod);

        // Data.
        private static int NEXT_NODE_ID;
        private int _ID = NEXT_NODE_ID++;
        private Transition _Transition;
        private HashSet<Node> _EpsilonTransitions = new HashSet<Node>();

        // Constructor.
        public Node() {
            // Nothing to do.
        }

        // Constructor with a transition.
        public Node(Transition trans) {
            // Store transition.
            _Transition = trans;
        }

        // Check whether transition is set up.
        public bool HasTransition {
            get {
                // Return transition.
                return _Transition != null;
            }
        }

        // Fetch transition.
        public Transition Transition {
            get {
                // Return transition.
                return _Transition;
            }
        }

        // Fetch epsilon transitions.
        public IEnumerable<Node> EpsilonTransitions {
            get {
                // Fetch epsilon transition list.
                return _EpsilonTransitions;
            }
        }

        // Add an epsilon transition.
        public void AddEpsilonTransition(Node dest) {
            // Attach new epsilon transition (only if we're not attaching ourselves).
            Debug.Assert(dest != this, "Trying to make Epsilon transition back to the same node");
            _EpsilonTransitions.Add(dest);
        }

        // Clone a node.
        public void Clone(Dictionary<Node, Node> clones, Stack<Node> toprocess, CharRange.Process proc, Process nproc) {
            // Loop over actual transitions, cloning them.
            Node node = clones[this];
            if( _Transition != null ) {
                // Fetch target node.
                Node dst;
                if( !clones.TryGetValue(_Transition.Destination, out dst) ) {
                    // Need to create target node.
                    clones[_Transition.Destination] = dst = new Node();
                    toprocess.Push(_Transition.Destination);
                }

                // Enqueue new (copied) transition.
                if( proc != null )
                    // Apply a character process during transition.
                    node._Transition = new Transition(proc(_Transition.Chars), dst);
                else
                    // Use old character transition range verbatim.
                    node._Transition = new Transition(_Transition.Chars, dst);
            }

            // Loop over epsilon transitions, cloning them.
            foreach( Node trans in _EpsilonTransitions ) {
                // Fetch target node.
                Node dst;
                if( !clones.TryGetValue(trans, out dst) ) {
                    // Need to create target node.
                    clones[trans] = dst = new Node();
                    toprocess.Push(trans);
                }

                // Enqueue new copied epsilon transition.
                node._EpsilonTransitions.Add(dst);
            }

            // Process the node when there is a node processor.
            if( nproc != null )
                nproc(this);
        }

        // Print a node.
        public void Print(Dictionary<Node, int> numbered, Stack<Node> toprocess, ref int nextidx) {
            // Fetch id.
            Console.WriteLine("Node ID {0}", numbered[this]);

            // Check for transition.
            if( _Transition != null ) {
                // Fetch target idx.
                int target;
                if( !numbered.TryGetValue(_Transition.Destination, out target) ) {
                    // Give new number to target and queue.
                    numbered[_Transition.Destination] = target = nextidx++;
                    toprocess.Push(_Transition.Destination);
                }

                // Display transition.
                Console.WriteLine("{0} -> {1}", _Transition.Chars, target);
            }

            // Walk epsilon transitions.
            foreach( Node trans in _EpsilonTransitions ) {
                // Fetch target idx.
                int target;
                if( !numbered.TryGetValue(trans, out target) ) {
                    // Give new number to target and queue.
                    numbered[trans] = target = nextidx++;
                    toprocess.Push(trans);
                }

                // Display transition.
                Console.WriteLine("e -> {0}", target);
            }
        }

        /// <summary>
        /// Compare the nodes, returning an integer defining their relation.
        /// </summary>
        /// <param name="other">Object to compare against.</param>
        /// <returns>Relation between the two Nodes.</returns>
        public int CompareTo(Node other) {
            // Return comparison of IDs.
            return _ID.CompareTo(other._ID);
        }

    }

    // Transition.
    internal class Transition {

        // Data.
        private CharRange _Chars;
        private Node _Destination;

        // Constructor.
        public Transition(CharRange chars, Node dest) {
            // Store data.
            _Chars = chars;
            _Destination = dest;
        }

        // Transition.
        public CharRange Chars {
            get {
                // Return transition.
                return _Chars;
            }
        }

        // Destination node.
        public Node Destination {
            get {
                // Return destination node.
                return _Destination;
            }
        }

    }

    // Tree repeat count.
    internal class RepeatCount {

        // Data.
        private int _From;
        private int? _To;

        // Constructor with only from count.
        public RepeatCount(int from) {
            // Set up only from count.
            _From = from;
        }

        // Constructor with to count.
        public RepeatCount(int from, int to) {
            // Set up both counts.
            _From = from;
            _To = to;
        }

        // Access from count.
        public int From {
            get {
                // Return from count.
                return _From;
            }
        }

        // Has to count.
        public bool HasTo {
            get {
                // Return state of to count.
                return _To.HasValue;
            }
        }

        // Access to count.
        public int To {
            get {
                // Return to value.
                return _To.Value;
            }
        }

    }

}
